Wireless communications networks have found great utility in many commercial and military applications. However, some types of wireless networks become less efficient in transmitting information when a large number of nodes are attempting to communicate thereon.
Previous efforts to increase the efficiency of a wireless network have included the following, all of which are assigned to the same entity as the present application and which are incorporated by reference herein in their entirety:
U.S. Pat. No. 5,949,760, entitled “Simultaneous Channel Access Transmission Method and a Multi-Hop Communications Radio Network”;
U.S. Pat. No. 5,719,868, titled “Dynamic Distributed, Multi-Channel Time Division Multiple Access Slot Assignment Method for a Network of Nodes”;
U.S. Pat. No. 6,487,186, titled “A Method and Apparatus for Managing Communication Resources Using Bootstrap Slots”;
U.S. Pat. No. 6,504,829, titled “A Method and Apparatus for Managing Communication Resources Using Channelized Neighborhoods”;
U.S. Pat. No. 6,628,636, titled “A Method and Apparatus for Managing Communication Resources Using Neighbor Segregation”;
U.S. Pat. No. 6,317,436, titled “A Method and Apparatus for Managing Communication Resources Using an Adaptive Broadcast Cycle (ABC)”;
U.S. Pat. No. 6,331,973, titled “Unifying Slot Assignment Protocol Multiple Access System”;
U.S. Pat. No. 6,574,206, titled “A Method and Apparatus for Managing Communication Resources Using Speculation Slots”;
U.S. Pat. No. 6,600,754, titled “A Method and Apparatus for Managing Communication Resources Using Standby Slots”;
U.S. Pat. No. 6,574,199, titled “Unifying Slot Assignment Protocol Logical Neighborhooding”; and
U.S. patent application Ser. No. 10/689,448, filed Oct. 20, 2003, titled “Heuristics for Combining Inter-Channel and Intra-Channel Communications in a Wireless Communications Environment.”
One challenge in efficiently managing networks with large numbers of nodes is maximizing the use of all communication slots. Typically each node in a network is assigned specific time slots in which to transmit messages or other information. A time slot may be assigned to a node either on a one-time basis, or the node may be assigned a time slot each time the time slot occurs in a repeating frame or time cycle. In either case, it is possible that a node has no messages or information to transmit during the time slot assigned to it, and the time slot would be wasted if not assigned to another node in the network. In addition, there may be some time slots that are not assigned or allocated to any node in the network.
One possible method of allocating unused time slots is to have slots report unused time slots to a central network controlling authority. However, such a central authority may not be immediately accessible to all nodes in a network, and by the time the central authority is advised of the existence of an unused slot, there may not be enough time to assign the time slot to a node that needs to use the slot.
Another challenge is allocating or re-assigning time slots in a network in which there are inherent constraints in the communication protocol of the network. For example, if the network is using principles of the Unifying Slot Assignment Protocol, certain nodes may not be able to have time slots re-assigned to them. This is because one of the USAP rules is that nodes less than three hops apart are not permitted to simultaneously use a time slot. Allocating or re-assigning a time slot to a node less than three hops from another node already using the time slot would violate this USAP rule and would cause conflicting transmissions to be sent across the network.
It is therefore an object of the invention to provide a method of allocating or re-assigning unused time slots.
It is another object of the invention to provide a method of re-assigning unused time slots that is consistent with other communications protocols, such as USAP.
It is still another object of the invention to provide a method of allocating or re-assigning unused time slots that does not depend on a central network authority to decide which nodes are to be awarded the re-assigned slots.
A feature of the invention is the sharing of information between nearby nodes to determine which of the nearby nodes is permitted to use an otherwise unused time slot.
An advantage of the invention is a de-centralized decision structure that efficiently and quickly re-assigns or re-allocates unused or unassigned time slots.